package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/9/9.<br><br>
 *
 * 中等：交错字符串（动态规划）
 */
public class Topic97 {

    public static void main(String[] args) {
        Topic97 instance = new Topic97();

        System.out.println(instance.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
        System.out.println(instance.isInterleave("", "", ""));
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();

        if(len1 + len2 != len3) {
            return false;
        }

        boolean[] map = new boolean[len2 + 1];
        map[0] = true;

        for(int i = 0; i <= len1; i++) {
            for(int j = 0; j <= len2; j++) {
                int k = i + j - 1;
                if(i > 0) {
                    map[j] = map[j] && s1.charAt(i - 1) == s3.charAt(k);
                }

                if(j > 0) {
                    map[j] = map[j] || map[j - 1] && s2.charAt(j - 1) == s3.charAt(k);
                }
            }
        }

        return map[len2];
    }

    public boolean isInterleave2(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();

        if(len1 + len2 != len3) {
            return false;
        }

        boolean[][] map = new boolean[len1 + 1][len2 + 1];
        map[0][0] = true;

        for(int i = 0; i <= len1; i++) {
            for(int j = 0; j <= len2; j++) {
                int k = i + j - 1;
                if(i > 0 && map[i - 1][j] && s1.charAt(i - 1) == s3.charAt(k)) {
                    map[i][j] = true;
                }

                if(j > 0 && map[i][j - 1] && s2.charAt(j - 1) == s3.charAt(k)) {
                    map[i][j] = true;
                }
            }
        }

        return map[len1][len2];
    }
}
